package org.cos.generation.util.agorithm;

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

import org.cos.generation.epda.State;
import org.cos.generation.epda.State.Transition;

public class Reachedable {
	
	private State[] states;
	
	private boolean[] visited;
	
	private List<Set<Integer>> reachedList;
	
	public List<Set<Integer>> nullReachedable(State[] states) {
		this.states = states;
		int size = states.length;
		visited = new boolean[size];

		reachedList = new ArrayList<Set<Integer>>(size);
		for (int i = 0; i < size; i++) {
			reachedList.add(new TreeSet<Integer>());
		}
		// DFS from every non-visited state.
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) visited[j] = false;
			nullDfs(i);
			for (int j = 0; j < size; j++) 
				if (visited[j] && i != j) reachedList.get(j).add(i);
		}
		return reachedList;
	}
	
	private void nullDfs(int index) {
		if (states[index] != null) {
			visited[index] = true;
			for (Transition trans : states[index].getTransitions()) {
				if (trans.getMethod() == null) {
					Integer tail = trans.getTailIndex();
					if (!visited[tail]) {
						nullDfs(tail);
					}
				}
			}
		}
	}
	
}
